package com.xgh.link;

import com.xgh.ListNode;

/**
 * @ClassName Link1
 * @Description
 * @Author xinggh
 * @Date 2020/7/17 23:21
 * @Version 1.0
 **/
public class Link1 {


    /**
     * 328. 奇偶链表
     * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
     * <p>
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     * <p>
     * 示例 1:
     * <p>
     * 输入: 1->2->3->4->5->NULL
     * 输出: 1->3->5->2->4->NULL
     * 示例 2:
     * <p>
     * 输入: 2->1->3->5->6->4->7->NULL
     * 输出: 2->3->6->7->1->5->4->NULL
     *
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        ListNode f3 = second.next;
        first.next = null;
        second.next = null;
        ListNode f1 = first;
        ListNode s2 = second;

        int n = 1;
        while (f3 != null) {
            if (n % 2 == 1) {
                f1.next = f3;
                f3 = f3.next;
                f1 = f1.next;
                f1.next = null;
            } else {
                s2.next = f3;
                f3 = f3.next;
                s2 = s2.next;
                s2.next = null;
            }

            n++;
        }
        f1.next = second;
        return first;
    }

    public static ListNode oddEvenList2(ListNode head) {
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;

        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;

        oddEvenList(l1);
    }
}
